package com.hy.study.practice.linkedlist;

import java.util.Stack;

/**
 * 单链表的操作
 */
public class SingleLinkedListDemo2 {
    public static void main(String[] args) {
        Studnet zhangsan = new Studnet(1, "张三");
        Studnet lisi = new Studnet(2, "李四");
        Studnet wangwu = new Studnet(3, "王五");
        Studnet zhaoliu = new Studnet(4, "赵六");

        StudentLinkedList studentLinkedList = new StudentLinkedList();
        studentLinkedList.add(zhangsan);
        studentLinkedList.add(lisi);
        studentLinkedList.add(wangwu);
        studentLinkedList.add(zhaoliu);
        studentLinkedList.show();



        Studnet zhangsan11 = new Studnet(11, "张三");
        Studnet lisi22 = new Studnet(22, "李四");
        Studnet wangwu33 = new Studnet(33, "王五");
        Studnet zhaoliu44 = new Studnet(44, "赵六");


        StudentLinkedList studentLinkedList22 = new StudentLinkedList();
//        studentLinkedList22.add(zhangsan11);
//        studentLinkedList22.add(lisi22);
//        studentLinkedList22.add(wangwu33);
//        studentLinkedList22.add(zhaoliu44);
        studentLinkedList22.show();

        System.out.println("=====================合并之后====================");

        StudentLinkedList resultMagerLinkedList = magerLinkedList(studentLinkedList, studentLinkedList22);
        resultMagerLinkedList.show();


        System.out.println("----------------利用栈将链表倒叙打印-----------");
        studentLinkedList.reversePrint();

        System.out.println("------------排序添加之后的-------------------");
        StudentLinkedList studentLinkedListOrderby = new StudentLinkedList();
        Studnet tianqi = new Studnet(5, "田七");
        studentLinkedListOrderby.addOrderByNumber(zhangsan);
        studentLinkedListOrderby.addOrderByNumber(lisi);
        studentLinkedListOrderby.addOrderByNumber(tianqi);
        studentLinkedListOrderby.addOrderByNumber(wangwu);
        studentLinkedListOrderby.addOrderByNumber(wangwu);
        studentLinkedListOrderby.addOrderByNumber(zhaoliu);
        studentLinkedListOrderby.show();
        System.out.println("------------------修改之后的-------------------");
        Studnet tianqi2 = new Studnet(5, "田七2222");
        studentLinkedListOrderby.update(tianqi2);
        studentLinkedListOrderby.show();

        studentLinkedListOrderby.delete(4);
        System.out.println("----------------删除操作之后的数据--------------");
        studentLinkedListOrderby.show();
        System.out.println("查询到number=7:" + studentLinkedListOrderby.get(7));
        System.out.printf("当前链表元素个数%d\n", studentLinkedListOrderby.length());
        System.out.println("查询倒数第1个元素是:" + studentLinkedListOrderby.getLastIndex(2));
        studentLinkedListOrderby.reverse();
        System.out.println("-----------------反转之后的链表----------------");
        studentLinkedListOrderby.show();

    }
    /**
     * 合并两个有序的单链表，合并之后的链表依然有序
     *
     * @return
     */
    public static StudentLinkedList magerLinkedList(StudentLinkedList first, StudentLinkedList second) {
        StudentLinkedList resultLinkedList = new StudentLinkedList();
        copyOrderBy(first, resultLinkedList);
        copyOrderBy(second, resultLinkedList);
        return resultLinkedList;
    }

    /**
     * 按顺序copy 链表
     *
     * @param first
     * @param resultLinkedList
     * @return
     */
    private static void copyOrderBy(StudentLinkedList first, StudentLinkedList resultLinkedList) {
        //先将第一个数组复制过来
        Studnet temp = first.getHead().getNextStudnet();
        Studnet resultTemp = resultLinkedList.getHead();
        while (temp != null) {
            int number = temp.getNumber();
            Studnet tempNextNext = temp.getNextStudnet();
            boolean falg = false;
            while (true) {
                if (resultTemp.getNextStudnet() == null) {//找到最后了
                    falg = true;
                    break;
                }
                if (resultTemp.getNextStudnet().getNumber() > number) {
                    falg = true;
                    break;
                } else if (resultTemp.getNextStudnet().getNumber() == number) {
                    break;
                }
                resultTemp = resultTemp.getNextStudnet();
            }
            if (falg) {
                temp.setNextStudnet(resultTemp.getNextStudnet());
                resultTemp.setNextStudnet(temp);
                temp = tempNextNext;
            }
        }
    }
}

/**
 * 一个学生的具有头节点的单链表
 */
class StudentLinkedList {

    private Studnet head = new Studnet();

    /**
     * 给外界提供一个获取头节点的方法
     *
     * @return
     */
    public Studnet getHead() {
        return head;
    }

    /**
     * 向队列中添加一个元素
     *
     * @param studnet
     */
    public void add(Studnet studnet) {
        Studnet temp = head;
        while (true) {
            if (temp.getNextStudnet() == null) {
                //找到了添加的位置
                break;
            }
            temp = temp.getNextStudnet();
        }
        temp.setNextStudnet(studnet);
    }

    /**
     * 根据学生编码进行排序添加
     *
     * @param studnet
     */
    public void addOrderByNumber(Studnet studnet) {
        Studnet temp = head;
        boolean falg = false;//判断是否 真的找到了
        while (true) {
            if (temp.getNextStudnet() == null) {//第一个
                falg = true;
                break;
            }
            if (temp.getNextStudnet().getNumber() > studnet.getNumber()) {
                //找到了添加的位置
                falg = true;
                break;
            } else if (temp.getNextStudnet().getNumber() == studnet.getNumber()) {
                System.out.println("队列中已经存在该值");
                break;
            }
            temp = temp.getNextStudnet();
        }
        if (falg) {
            //修改指针信息
            studnet.setNextStudnet(temp.getNextStudnet());
            temp.setNextStudnet(studnet);
        } else {
            System.out.println("没有找到合适的插入位置");
        }

    }

    /**
     * 修改链表中的指定元素
     *
     * @param studnet
     */
    public void update(Studnet studnet) {
        if (head.getNextStudnet() == null) {
            System.out.println("链表为空 无法更新");
            return;
        }
        boolean flag = false;
        Studnet temp = head.getNextStudnet();
        while (temp != null) {
            if (temp.getNumber() == studnet.getNumber()) {
                flag = true;
                break;
            }
            temp = temp.getNextStudnet();
        }
        if (flag) {
            temp.setName(studnet.getName());
        }
    }

    /**
     * 删除指定链表的指定ID对应的对象
     *
     * @param number 元素的唯一标识
     */
    public void delete(int number) {
        if (head.getNextStudnet() == null) {
            System.out.println("链表为空,无法删除");
            return;
        }
        boolean flag = false;
        Studnet temp = head;
        while (true) {
            if (temp.getNextStudnet() == null) {//找到最后了
                break;
            }
            if (temp.getNextStudnet().getNumber() == number) {//找到了
                flag = true;
                break;
            }
            temp = temp.getNextStudnet();
        }
        //修改指针的指向
        if (flag) {
            temp.setNextStudnet(temp.getNextStudnet().getNextStudnet());
        } else {
            System.out.println("么有知道需要删除的数据");
        }

    }

    /**
     * 显示当前链表的信息
     */
    public void show() {
        if (head.getNextStudnet() == null) {
            System.out.println("链表为空");
            return;
        }
        Studnet temp = head.getNextStudnet();
        while (temp != null) {
            System.out.println(temp);
            temp = temp.getNextStudnet();
        }
    }

    /**
     * 根据指定的ID查询数据
     *
     * @param number
     * @return
     */
    public Studnet get(int number) {
        if (head.getNextStudnet() == null) {
            return null;
        }
        Studnet temp = head.getNextStudnet();
        boolean flag = false;
        while (temp != null) {
            if (temp.getNumber() == number) {
                flag = true;
                break;
            }
            temp = temp.getNextStudnet();
        }
        if (flag) {
            return temp;
        } else {
            return null;
        }

    }

    /**
     * 获取当前链表的长度
     *
     * @return
     */
    public int length() {
        if (head.getNextStudnet() == null) {
            return 0;
        }
        Studnet temp = head.getNextStudnet();
        int count = 0;
        while (temp != null) {
            count++;
            temp = temp.getNextStudnet();
        }
        return count;
    }

    /**
     * 查询单链表倒数第k个节点
     *
     * @param index 指定的倒数的 位
     * @return
     */
    public Studnet getLastIndex(int index) {
        if (head.getNextStudnet() == null) {
            return null;
        }
        if (index < 0 || index > length()) {
            return null;
        }
        //遍历到 (size-index).next 就是需要的元素
        Studnet temp = head.getNextStudnet();
        int count = 0;
        while (temp != null) {
            if ((length() - count) == index) {
                return temp;
            }
            temp = temp.getNextStudnet();
            count++;
        }
        return null;
    }

    /**
     * 将当前列表反转输出
     */
    public void reverse() {
        if (head.getNextStudnet() == null) {
            return;
        }
        Studnet temp = head.getNextStudnet();
        Studnet newHead = new Studnet();//创建一个新的头队列
        while (temp != null) {
            Studnet tempNext = temp.getNextStudnet();
            temp.setNextStudnet(newHead.getNextStudnet());
            newHead.setNextStudnet(temp);
            temp = tempNext;
        }
        head.setNextStudnet(newHead.getNextStudnet());
    }

    /**
     * 从尾到头打印单链表 但不改变链表的结构
     * 使用栈配合 将遍历的数据存入到栈中  利用栈的先进后出 实现遍历
     */
    public void reversePrint() {
        if (head.getNextStudnet() == null) {
            return;
        }
        Studnet temp = head.getNextStudnet();
        Stack<Studnet> studnetStack = new Stack<Studnet>();
        while (temp != null) {
            studnetStack.push(temp);
            temp = temp.getNextStudnet();
        }
        while (studnetStack.size() > 0) {
            System.out.println(studnetStack.pop());
        }
    }
}

/**
 * 学生实体
 */
class Studnet {
    private int number;
    private String name;
    private Studnet nextStudnet;

    public Studnet(int number, String name) {
        this.number = number;
        this.name = name;
    }

    public Studnet() {
    }

    public int getNumber() {
        return number;
    }

    public void setNumber(int number) {
        this.number = number;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public Studnet getNextStudnet() {
        return nextStudnet;
    }

    public void setNextStudnet(Studnet studnet) {
        this.nextStudnet = studnet;
    }

    @Override
    public String toString() {
        return "Studnet{" +
                "number=" + number +
                ", name='" + name + '\'' +
                '}';
    }
}